package own.stu.jobgib.playown.alg.solution.dp;

import java.util.Arrays;

/**
 * 背包型dp
 * <p>
 * <li/>你有一人背包，背包有最大承重
 * <li/>都是免费拿商店里有若干物品，
 * <li/>每个物品有重量和价值
 * <li/>目标:不撑爆背包的前提下
 * <li/>-装下最多重量物品
 * <li/>-装下最大总价值的物品
 * <li/>-有多少种方式正好带走满满一书包物品
 * <p>
 * <li/>总结
 * <li/>Backpack 可行性背句
 * <li/>- 题目要求最多装多少重量
 * <li/>- 记录前i个物品能不能拼出重量w
 * <li/>Backpack V,Backpack Vl,计数型背包
 * <li/>- 题目要求有多少种方式装出重量
 * <li/>- Backpack V: 记录前i个物品有多少种方式拼出重量W
 * <li/>- Backpack V: 记录有多少种方式拼出重量W
 * <li/>Backpackll,BackpackIll,最值型背包
 * <li/>- 题面，要求能拼出的最大价值
 * <li/>- 记录f][w]=前i个/种物品拼出重量w能得到的最大价值
 * <li/>关键点
 * <li/>-最后一步
 * <li> . 最后一个背包内的物品是哪个
 * <li/>- 数组大小和最大承重Target有关
 */
public class BackPackType {

    public static void main(String[] args) {
        BackPackType b = new BackPackType();
        // System.out.println(b.backPack(10, new int[]{3, 4, 8, 5}));
        // System.out.println(b.backPackV(new int[]{1, 2, 3, 3, 7}, 7));
        // System.out.println(b.backPackV(new int[]{1, 1, 1, 1}, 3));

        // System.out.println(b.backPackVI(new int[]{1, 2, 4}, 4));
        // System.out.println(b.backPackVI(new int[]{1, 2}, 4));


        // System.out.println(b.backPackII(10, new int[]{2, 3, 5, 7}, new int[]{1, 5, 2, 4}));
        // System.out.println(b.backPackII(10, new int[]{2, 3, 8}, new int[]{2, 5, 8}));
        // System.out.println(b.backPackII(100, new int[]{77, 22, 29, 50, 99}, new int[]{92, 22, 87, 46, 90}));

        //System.out.println(b.backPackIII(new int[]{2, 3, 5, 7}, new int[]{1, 5, 2, 4}, 10));

        //System.out.println(b.kSum(new int[]{1, 2, 3, 4}, 2, 5));
        System.out.println(b.kSum(new int[]{1, 2, 3, 4, 5, 2}, 3, 6));
    }

    /**
     * 92 · 背包问题
     * 描述 在 n 个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A(i)
     * （每个物品只能选择一次且物品大小均为正整数）
     * <p>
     * 你不可以将物品进行切割
     * <p>
     * 样例 1：
     * 输入：数组 = [3,4,8,5] backpack size = 10
     * 输出：9
     */
    public int backPack(int m, int[] a) {
        /*
        dp[i]表示是否能够装满
        dp[i - a[j]] (i >= a[j])
        --- 为什么不能只考虑物品，是因为物品的不一定会装入到背包中，因此需要两个维度 重量和大小
        dp[i][w] 能否用前i个物品拼出重量w
        dp[i][w]
        1: dp[i - 1][w] 前i-1 已经能够拼出
        2: dp[i - 1][w-a[i - 1]] (w>a[i-1])

        dp[0][0] = true;

         */
        if (a == null || a.length == 0 || m <= 0) {
            return 0;
        }
        int n = a.length;
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= a[i - 1])
                    dp[i][j] |= dp[i - 1][j - a[i - 1]];
            }
        }
        for (int i = m; i >= 1; i--) {
            if (dp[n][i]) {
                return i;
            }
        }
        return 0;
    }

    /**
     * 563 · 背包问题（五）
     * 给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
     * 每一个物品只能使用一次
     * 样例
     * <p>
     * 输入：
     * nums = [1,2,3,3,7] target = 7
     * 输出：2
     * 解释： 结果的集合为: [7] [1,3,3] 返回 2
     */
    public int backPackV(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target <= 0) {
            return 0;
        }
        int n = nums.length;
        /*
         * dp[i][w] 前i个物品多少种方式拼出重量w
         * dp[i - 1][w] 前i-1个物品已经能够拼出w  **重点**
         * dp[i - 1][w - a[i - 1]]，前i-1个物品能够拼出 w-a[i-1]，加上当前物品i-1，可以拼出w
         *
         * 初始值
         * dp[0][0] = 1;// 一种方式
         * dp[0][i] = 0;// 不能拼出，0种方式
         */
        int[][] dp = new int[n + 1][target + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= target; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w - nums[i - 1] >= 0) {
                    dp[i][w] += dp[i - 1][w - nums[i - 1]];
                }
            }
        }
        return dp[n][target];
    }

    /**
     * 564 · 背包问题 IV
     * 给出一个都是正整数的数组 nums，其中没有重复的数。从中找出所有的和为 target 的组合个数。
     * <p>
     * 一个数可以在组合中出现多次。
     * 数的顺序不同则会被认为是不同的组合。
     * 1≤nums.length≤100
     * 1≤nums[i]≤1000
     * 1≤target≤1000
     * <p>
     * 样例
     * <p>
     * 输入: nums = [1, 2, 4] 和 target = 4
     * 输出: 6
     * 解释:
     * 可能的所有组合有：
     * [1, 1, 1, 1]
     * [1, 1, 2]
     * [1, 2, 1]
     * [2, 1, 1]
     * [2, 2]
     * [4]
     */
    public int backPackVI(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target <= 0) {
            return 0;
        }
        int n = nums.length;
        /*
        没有重量，只有数量1个维度
        dp[i] 组成数字i的 组合个数
        dp[i - nums[j]] （i - nums[j] >= 0 && dp[i - nums[j]] 可以组成（j = 0..

        dp[0] = 1; 因为 dp[nums[0]] = 1 ，推到时讲dp[0] = 1 方便计算
         */
        int[] dp = new int[target + 1];
        // Arrays.fill(dp, -1);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < n; j++) {
                if (i - nums[j] >= 0) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }

    /**
     * 125 · 背包问题（二）
     * 有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.
     * 问最多能装入背包的总价值是多大?
     * <p>
     * A[i], V[i], n, m 均为整数
     * 你不能将物品进行切分
     * 你所挑选的要装入背包的物品的总大小不能超过 m
     * 每个物品只能取一次
     * m<=1000
     * len(A),len(V)<=100
     * <p>
     * 样例
     * <p>
     * 输入：
     * m = 10 A = [2, 3, 5, 7] V = [1, 5, 2, 4]
     * 输出：9
     * 解释：装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9
     */
    public int backPackII(int m, int[] a, int[] v) {
        if (a == null || a.length == 0 || m <= 0) {
            return 0;
        }
        /*
        dp[i][j] 表示前i个物品，大小j的最大总价值
        max(
        dp[i - 1][j] 前i-1个物品已经拼出了大小j
        dp[i][j - a[i - 1]] + v[i - 1] 前i-1个物品拼出了j-a[i-1](j - a[i-1] >=0)
        )
        dp[0][0] = 0;
        dp[0][i] = -1 表示0个物品不能拼出大小i
         */
        int n = a.length;
        int[][] dp = new int[n + 1][m + 1];
        Arrays.fill(dp[0], -1);
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - a[i - 1] >= 0 && dp[i - 1][j - a[i - 1]] != -1)
                    dp[i][j] = Math.max(dp[i - 1][j - a[i - 1]] + v[i - 1], dp[i][j]);
            }
        }

        int max = 0;
        for (int i = 1; i <= m; i++) {
            max = Math.max(max, dp[n][i]);
        }
        return max;
    }

    /**
     * 440 · 背包问题（三）
     * 给定 n 种物品, 每种物品都有无限个. 第 i 个物品的体积为 A[i], 价值为 V[i].
     * <p>
     * 再给定一个容量为 m 的背包. 问可以装入背包的最大价值是多少?
     * <p>
     * 不能将一个物品分成小块.
     * 放入背包的物品的总大小不能超过 m.
     * 样例
     * 样例 1:
     * <p>
     * 输入: A = [2, 3, 5, 7], V = [1, 5, 2, 4], m = 10
     * 输出: 15
     * 解释: 装入三个物品 1 (A[1] = 3, V[1] = 5), 总价值 15.
     */
    public int backPackIII(int[] a, int[] v, int m) {
        if (a == null || a.length == 0 || m <= 0) {
            return 0;
        }

        int n = a.length;
        /*
        没有重量，只有数量1个维度
        dp[i] 组成数字i的 最大价值
        dp[i - nums[j]] （i - nums[j] >= 0 && dp[i - nums[j]] 可以组成（j = 0..

        dp[0] = 0;
         */
        int[] dp = new int[m + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {

                int tmpWeight = i - a[j];
                if (tmpWeight >= 0 && dp[tmpWeight] != -1) {
                    dp[i] = Math.max(dp[tmpWeight] + v[j], dp[i]);
                }
            }
        }
        int max = 0;
        for (int i : dp) {
            max = Math.max(max, i);
        }
        return max;
    }

    /**
     * 89 · K数之和
     * 给定 n 个不同的正整数，整数 k(k≤n)以及一个目标数字 target。
     * 在这 n 个数里面找出 k 个数，使得这 k 个数的和等于目标数字，求问有多少种方案？
     * <p>
     * 样例：
     * 输入：A = [1,2,3,4] k = 2 target = 5
     * 输出：2
     */
    public int kSum(int[] a, int K, int target) {
        if (a == null || a.length <= 0 || target <= 0 || a.length < K) {
            return 0;
        }
        int n = a.length;
        /*
        dp[i][k][j] 表示前i个个数中 找出k个数字 的和为j的方案数
        dp[i][k][j] =
        dp[i - 1][k][j] 不使用数字a[i]
        dp[i - 1][k - 1][j - a[i]]  使用数字a[i]

        dp[0][0][j] = 0;
        dp[0][0][0] = 1;
         */
        int[][][] dp = new int[n + 1][K + 1][target + 1];
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int k = 0; k <= i && k <= K; k++) {
                for (int j = 0; j <= target; j++) {
                    dp[i][k][j] = dp[i - 1][k][j];
                    if (k > 0 && j >= a[i - 1]) {
                        dp[i][k][j] += dp[i - 1][k - 1][j - a[i - 1]];
                    }
                }
            }
        }
        return dp[n][K][target];
    }
}
